今日挑選題目的理由是看到吳邦一教授在 counter (計步器)中值域這小標裡解的兩道題目

Counter 是 紀錄字符或數字等出現的次數,常用 hash table實現。hash table 有 O(1) 的讀寫，空間需要 O(N)。
然而當任務的值域已知夠小，那就用陣列代替 hash table，這樣就能將空間複雜度會降到 O(1) ，因為不會隨著輸入增長。

299. Bulls and Cows (Medium)

題目敘述:
幾A幾B的遊戲。給謎底 (secret)與玩家猜的字串(guess)，
最終返回 xAyB 的字串。
x 是 guess的 char 與 secret 的char 相同且位置也相同(A)的數量
y 是 guess的 char 與 secret 的 char 相同但位置不相同(B)的數量

**解題想法: **
A 跟 B 數量計算是有優先級問題的，同一個字元被拿去用來算 A 就不會用來算 B。

然而先算完 A ，算 B 時還要排除 A 的情況算太麻煩 因此我解題改成算完所有 guess 與 secret 重疊的字母的數量，這數量再減掉 A 得到 B 數量。

class Solution {
public:
    string getHint(string secret, string guess) {
        int i = 0, a = 0, b = 0;
        vector<int>guess_mp(10, 0);

        for (char s: secret) {
            guess_mp[s - '0'] += 1;            
        }
        for (int i = 0; i < guess.size(); i++) {
            char digit = guess[i];
            if (secret[i] == digit)
                a += 1;
            if (guess_mp[digit - '0'] > 0) {
                b += 1;
                guess_mp[digit - '0'] -= 1;
            }
        }
        b -= a;
        return to_string(a) + 'A' + to_string(b) + 'B';
    }
};

時間複雜度: O(N); 空間複雜度：O(1)

註: Leetcode 測 run time 不準，我用陣列比用 hash 時的 run time 還長。

1347. Minimum Number of Steps to Make Two Strings Anagram (Medium)

題目敘述:
給兩個長度相同的字串 s 和 t。在一個步驟中，您可以選擇 t 的任何字元並將其替換為另一個字元，問使 t 成為 s 的字謎詞(Anagram) 的最少步驟數。
p.s. Anagram 是指包含相同字元但順序不同（或相同）的字串。

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

解題想法:
在這個問題中，我們不在乎字符的順序，只要 t 和 s 包含相同的字符即可。因此用到 Counter

我的解題過程是想像自己拿著紅筆，把 s 與 t 都有出現的 chars 劃掉，接著計算每個字母的差異。
例如以上的輸入輸出: 劃掉後，s剩 'b', t剩 'a', 差異的字母數(diff)為2，最後，因為每一步可以替換一個字母，所以我們需要 diff/2 = 1步。 ("1"步: t 的 'a' 寫入 'b' 就好)

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int>s_count (26, 0);
        vector<int>t_count (26, 0); 
        for (int i = 0; i < s.size(); i++) {
            s_count[s[i] - 'a'] += 1;
            t_count[t[i] - 'a'] += 1;
        }

        int diff = 0;
        for (int i = 0; i < 26; i++) {
            if (s_count[i] != t_count[i]) {
                diff += abs(t_count[i] - s_count[i]);
            }
        }
        return diff/2;
    }
};

時間複雜度: O(N); 空間複雜度：O(1)